МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
«ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Я.П. Романчук
ДИСКРЕТНА МАТЕМАТИКА
Конспект лекцій
Розглянутий на засіданні кафедри АСУ
як навчальний посібник для студентів
базового напрямку 050101 «Комп’ютерні науки»
денної та заочної форм навчання (протокол № 1-10/11 від 31 серпня 2010 р.)
Львів − 2010
УДК 519.1+519.6
Я.П. Романчук. Дискретна математика: Конспект лекцій для студентів напряму комп’ютерні науки спеціальності Інформаційні управляючі системи та технології. – Львів: НУЛП, 2010. – 210 с.
У конспекті викладено теорію множин і відношень; алгебру логіки і алгебру логіки висловлень і предикатів, теорію графів, моделі алгоритмів і програм, формальні граматики й мови, основи теорії кодування та шифрування.
Кожен розділ складається з основних визначень, властивостей, операцій і теорем; має значну кількість розв’язаних і ілюстрованих прикладів з об’єктами дискретної природи; містить вправи для аудиторної та самостійної роботи студентів.
Конспект лекцій може бути корисним для студентів інших спеціальностей, які бажають вивчати методи дискретної математики для використання їх у природничих і гуманітарних науках із залученням інформаційних технологій.
Рецензент:
І.М. Дронюк, кандидат фізико-математичних наук, доцент кафедри АСУ.
Відповідальна за випуск:
З.Я. Шпак, кандидат технічних наук, доцент кафедри АСУ.
Лекція 3
4.6. Похідна від булевої функції.
У класичній математиці для з’ясування характеру зміни функції використовують поняття похідної. У дискретній математиці, що оперує логічними функціями змінних, котрі, як і самі функції, приймають значення 0 або 1, поняття похідної вводиться таким чином.
Означення 4.17. Одиничною залишковою функцією змінної називається функція, одержувана шляхом надання змінній значення одиниця:
Означення 4.18. Нульовою залишковою функцією змінної називається функція, одержувана шляхом надання змінній значення нуль:
.
Означення 4.19. Похідна першого порядку від булевої функції змінних є функція, одержувана додаванням за модулем 2 одиничних і нульових залишкових функцій змінної :
.
Дотримуючись означення 4.19, для знаходження похідної від булевої функції необхідно скласти одиничну і нульову залишкові функції, додати їх за модулем 2 і, використовуючи основні еквівалентності булевих функцій або таблиці істинності, по можливості спростити отримані вирази.
Приклад 4.23. Маємо функцію трьох змінних . Знайти , , .
Розв’язок: ;
;
.
Для спрощення отриманих виразів, складемо їхні таблиці істинності:
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
1
0
0
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
Остаточно маємо: , , .
Приклад 4.24. Маємо функцію . Знайти .
Розв’язок: За умовою змінна є фіктивною. Тому і одинична, і нульова залишкові функції змінної будуть однакові і збіжаться з . Оскільки , одержимо
.
Отже, похідна від булевої функції за фіктивною змінною тотожно дорівнює нулю.
Похідні вищих порядків від булевої функції знаходять як і похідні першого порядку відповідно до означення 4.19, але послідовно, причому в якості наступної функції виступає вже знайдений і спрощений вираз попередньої похідної.
Приклад 4.25. Маємо функцію трьох змінних . Знайти , , , , , , .
Розв’язок: ;
;
.
Спростимо отримані вирази за допомогою їх таблиць істинності:
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
1
1
1
0
1
1
0
1
1
0
0
1
1
0
1
1
1
1
1
0
Отже, використовуючи таблиці істинності, можемо записати ДДНФ отриманих функцій:
, , .
Знайдемо похідні вищих порядків:
, бо в виразі похідної функції змінна фіктивна;
;
;
.
Вправи:
1. Знайти похідні першого порядку , , від булевих функцій трьох змінних :
а) ; б) ;
в) ; г) ;
д) ; е) ;
ж) ; з) ;
и) ; к) .
Спростити отримані вирази.
2. Знайти похідні , , , , , , від...
